// https://www.lintcode.com/problem/number-of-airplanes-in-the-sky/description

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
// bool cmp (Interval &i1, Interval &i2) {
//     if (i1.start == i2.start) {
//         return i1.end < i2.end;
//     } else {
//         return i1.start < i2.start;
//     }
// }

// class Solution {
// public:
//     /**
//      * @param airplanes: An interval array
//      * @return: Count of airplanes are in the sky.
//      */
//     int countOfAirplanes(vector<Interval> &airplanes) {
//         int max = 0;
//         map<int, int> rec;
//         sort(airplanes.begin(), airplanes.end(), cmp);
//         for (Interval plane: airplanes) {
//             rec[plane.start]++;
//             rec[plane.end]--;   
//             if (rec[plane.start] > max) {
//                 max = rec[plane.start];
//             }
//         }
//         return max;
//     }
// };

// 扫描线标准写法
// 排序O(nlogn)，扫描O(n)
// class Event {
// public:
//     int time;
//     int flag; // 0 land, 1 take off
//     Event (int t, int f) {
//         this->time = t;
//         this->flag = f;
//     }
//     bool operator < (const Event& p) const {
//         return this->time < p.time || (this->time == p.time && this->flag < p.flag);
//     }
// };

// class Solution {
// public:
//     /**
//      * @param airplanes: An interval array
//      * @return: Count of airplanes are in the sky.
//      */
//     int countOfAirplanes(vector<Interval> &airplanes) {
//         int n = airplanes.size();
//         vector<Event> list;
//         for (Interval i: airplanes) {
//             list.push_back(Event(i.start, 1));
//             list.push_back(Event(i.end, 0));
//         }
//         sort(list.begin(), list.end());
//         int cnt = 0; 
//         int ans = 0;
//         for (Event p: list) {
//             if (p.flag == 1) {
//                 ++cnt;
//             } else {
//                 --cnt;
//             }
//             ans = max(ans, cnt);
//         }
//         return ans;
//     }
// };

// 法二：贪心+最小堆
// 首先对所有时间段按照起飞时间升序排序.
// 遍历这个序列, 遍历的过程中把当前的飞机的降落时间添加到小根堆中,
// 并把堆中所有小于当前飞机起飞时间的元素弹出.
// 此时的堆中储存的就是当前飞机在天上时, 同时还在天上的飞机.
// 对堆中元素数量取max得到答案
bool cmp(Interval& i1, Interval& i2) {
    return i1.start < i2.start || (i1.start == i2.start && i2.end < i2.end);
}
class Solution {
public:
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        int n = airplanes.size();
        sort(airplanes.begin(), airplanes.end(), cmp);
        // priority_queue<int> q; 
        priority_queue<int, vector<int>, greater<int>> q;
        //注意不是用单调栈，对比的是end和begin，存储的是end
        int res = 0;
        for (const auto& a: airplanes) {
            q.push(a.end);
            // while (q.top() < a.start) {
            while (q.top() <= a.start) {
                q.pop();
            }
            res = max(res, (int)q.size()); //std::priority_queue::size_type，需要转换
        }
        
        return res;
    }
};